package com.cqs.leetcode.dp;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * lixw
 * 2021/11/11
 **/
public class KInversePairsArray629 {

    public int kInversePairs(int n, int k) {
        long[][] dp = new long[n + 1][k + 1];
        //dp[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1; //自然序列
        }
        //一个元素的时候， 只可能有k = 1,的情况
        for (int j = 1; j <= k; j++) {
            dp[0][j] = 0;
        }
        int mod = 1000000007;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = ((dp[i - 1][j] + dp[i][j - 1])) % mod;
                if (j >= i) {
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i]);
                    if (dp[i][j] < 0) {
                        dp[i][j] += mod;
                    }
                }
                dp[i][j] %= 1000000007;
            }
        }
        return (int) dp[n][k];
    }

    public static void main(String[] args) {
        List<int[]> cases = new ArrayList<>();
        cases.add(new int[]{2, 1});
        cases.add(new int[]{3, 1});
        cases.add(new int[]{1000, 1000});
        KInversePairsArray629 k = new KInversePairsArray629();
        for (int[] t : cases) {
            System.out.println(ArraysUtils.formatInts(t) + " ---> " + k.kInversePairs(t[0], t[1]));
            ;
        }
    }
}
